1. Technical Field
The present invention relates to three-dimensional (3D) ball skinning.
2. Discussion of the Related Art
The geometric problem of ball skinning is the computation of a continuous interpolation of a discrete set of balls, for example. This problem arises in numerous applications, including character skinning, molecular surface model generation, and modeling of tubular structures, etc.
In computer animation, often an articulated object or character is constructed using a layered representation consisting of a skeletal structure and a corresponding geometric skin, see e.g., K. Singh, E. Kokkevis, Skinning Characters using Surface Oriented Free-Form Deformations, in: Graphics Interface, 2000, pp. 35-42. Here, the skeleton has fewer degrees of freedom and is simpler to adjust by an animator. Given a new skeletal pose, the skinning algorithm is responsible for deforming the geometric skin to respond to the motion of the underlying skeleton. The skinning problem is also a special case of the problem of computing the envelopes of families of quadrics, which have been investigated by Peternell in, M. Peternell, Rational Parameterizations for Envelopes of Quadric Families, Ph.D. thesis, University of Technology, Vienna, Austria (1997), via the use of cyclographic maps. Rossignac and Schaefer in, J. Rossignac, S. Schaefer, J-splines, Computer Aided Design 40 (10-11) (2008) 1024-132, presented J-splines, which produce smooth curves from a set of ordered points using a subdivision framework.
The problem of ball skinning appears frequently in the context of computational chemistry and molecular biology, when generating surface meshes for molecular models, see e.g., H. Cheng, X. Shi, Quality Mesh Generation for Molecular Skin Surfaces Using Restricted Union of Balls, in: IEEE Visualization, 2005, H. Edelsbrunner, Deformable smooth surface design, Discrete and Computational Geometry 21 (1) (1999) 87-115 and N. Kruithov, G. Vegter, Envelope Surfaces, in: Annual Symposium on Computational Geometry, 2006, pp. 411-420. Several algorithms exist to skin a molecular model to produce a C1 continuous surface that is tangent smooth and has high mesh quality. These methods are typically either based on Delaunay triangulation like Cheng's or by finding the isosurface of an implicit function like Kruithov's. The work of Kruithov et al. derives a special subset of skins that is piece-wise quadratic. When dealing with a continuous family of balls, the skin may be computed as the envelope of the infinite union of the circles of intersection of two consecutive balls of infinitely close center. While the surfaces generated by these methods are tangent to the balls and have smoothness at the point of tangency, none of these existing methods provides an optimally smooth skin.